package sort

import "github.com/1141520944/go-library/hjz/common"

func TestSort(val func([]int) []int) {
	if !common.EqSort(val, 20) {
		panic("----错误----")
		return
	}
	println("----通过----")
}
func Bubble(nums []int) []int {
	l := len(nums)
	if nums == nil || l < 2 {
		return nums
	}
	for i := l; i >= 0; i-- {
		for j := 0; j < i; j++ {
			if nums[j] > nums[j+1] {
				nums[j], nums[j+1] = nums[j+1], nums[j]
			}
		}
	}
	return nums
}
func SelectSort(nums []int) []int {
	l := len(nums)
	if nums == nil || l < 2 {
		return nums
	}
	for i := 0; i < l; i++ {
		minIndex := i
		for j := i + 1; j < l; j++ {
			if nums[j] < nums[minIndex] {
				minIndex = j
			}
		}
		if minIndex != i {
			nums[i], nums[minIndex] = nums[minIndex], nums[i]
		}
	}
	return nums
}
func InsertSort(nums []int) []int {
	l := len(nums)
	if nums == nil || l < 2 {
		return nums
	}
	for i := 0; i < l; i++ {
		key := nums[i]
		j := i - 1
		for j >= 0 && nums[j] > key {
			nums[j+1] = nums[j]
			j--
		}
		nums[j+1] = key
	}
	return nums
}
func ShellSort(nums []int) []int {
	l := len(nums)
	if nums == nil || l < 2 {
		return nums
	}
	mid := l >> 1
	for mid > 0 {
		for i := mid; i < l; i++ {
			key := nums[i]
			j := i - mid
			for j >= 0 && nums[j] > key {
				nums[j+mid] = nums[j]
				j -= mid
			}
			nums[j+mid] = key
		}
		mid = mid >> 1
	}
	return nums
}
func MergeSort(nums []int) []int {
	l := len(nums)
	if nums == nil || l < 2 {
		return nums
	}
	mid := l >> 1
	left := MergeSort(nums[:mid])
	right := MergeSort(nums[mid:])
	return Merge(left, right)
}
func Merge(left, right []int) (res []int) {
	l, r := 0, 0
	for l < len(left) && r < len(right) {
		if left[l] < right[r] {
			res = append(res, left[l])
			l++
		} else {
			res = append(res, right[r])
			r++
		}
	}
	res = append(res, left[l:]...)
	res = append(res, right[r:]...)
	return
}
func QuickSort(nums []int) []int {
	quick(nums, 0, len(nums)-1)
	return nums
}
func quick(nums []int, l, r int) {
	if l < r {
		i := partition(nums, l, r)
		quick(nums, l, i-1)
		quick(nums, i+1, r)
	}
}

func partition(arr []int, low, high int) int {
	key := arr[high]
	i := low - 1
	for j := low; j < high; j++ {
		if arr[j] < key {
			i++
			arr[i], arr[j] = arr[j], arr[i]
		}
	}
	index := i + 1
	arr[index], arr[high] = arr[high], arr[index]
	return index
}
